# -*- coding: utf-8 -*-
# @Time  : 2021/8/17 下午3:30
# @Author : huangyuan
# @Project : algorithm
# @FileName: DoubleLinkedList.py
# @Description 双向链表


# 节点类
class Node:
    def __init__(self, pre, next, item):
        self.pre = pre
        self.next = next
        self.item = item


# 双向链表
class DoubleLinkedList:
    def __init__(self):
        self.head = Node(None, None, None)
        self.tail = self.head
        self.size = 0

    def __iter__(self):
        return DoubleLinkedListIterator(self.head)

    # 在链表末尾添加元素
    def add(self, item):
        self.tail.next = Node(self.tail, None, item)
        self.tail = self.tail.next
        self.size += 1

    # 在链表头部添加元素
    def add_first(self, item):
        if self.is_empty():
            self.head.next = Node(self.head, None, item)
            self.tail = self.head.next
        else:
            # 获取当前链表的第一个节点
            first = self.head.next
            new_first = Node(self.head, first, item)
            first.pre = new_first
            self.head.next = new_first
        self.size += 1

    # 移除链表元素 从链表尾部移除
    def remove(self):
        if self.is_empty():
            raise RuntimeError("链表为空")
        self.tail = self.tail.pre
        self.tail.next = None
        self.size -= 1

    # 移除链表元素 从链表头部移除
    def remove_first(self):
        if self.is_empty():
            raise RuntimeError("链表为空")
        if self.size == 1:
            self.head.next = None
            self.tail = self.head
        else:
            first = self.head.next
            self.head.next = first.next
            first.next.pre = self.head
        self.size -= 1

    # 通过元素值删除元素
    def remove_value(self, item):
        if self.is_empty():
            raise RuntimeError("链表为空")
        head_next = self.head.next
        while head_next is not None:
            if head_next.item == item:
                # 链表只有一个节点
                if self.size == 1:
                    self.head.next = None
                    self.tail = self.head
                    return
                # 删除的是最后一个元素
                elif head_next.next is None:
                    self.tail = head_next.pre
                    self.tail.next = None
                else:
                    # 上一节点next 指向下一节点
                    head_next.pre.next = head_next.next
                    # 下一节点 pre 指向上一节点
                    head_next.next.pre = head_next.pre

            head_next = head_next.next
        self.size -= 1

    # 确定链表是否为空
    def is_empty(self):
        return self.size == 0


# 双向链表迭代器
class DoubleLinkedListIterator:
    def __init__(self, head):
        self.head = head

    def __iter__(self):
        return self

    def __next__(self):
        if self.head.next is None:
            raise StopIteration
        else:
            item = self.head.next.item
            self.head = self.head.next
        return item


if __name__ == '__main__':
    doubleLinkedList = DoubleLinkedList()
    doubleLinkedList.add(1)
    doubleLinkedList.add(2)
    doubleLinkedList.add(3)
    doubleLinkedList.add(4)
    for value in doubleLinkedList:
        print(value)
    print("---------------------")
    doubleLinkedList.remove()
    for value in doubleLinkedList:
        print(value)
    print("---------------------")
    doubleLinkedList.add_first(10)
    doubleLinkedList.remove()
    doubleLinkedList.add_first(4)
    for value in doubleLinkedList:
        print(value)
    print("---------------------")
    doubleLinkedList.add(111)
    doubleLinkedList.add(222)
    doubleLinkedList.add(333)
    doubleLinkedList.add(444)
    for value in doubleLinkedList:
        print(value)
    print("---------------------")
    doubleLinkedList.remove_value(10)
    for value in doubleLinkedList:
        print(value)
    print("---------------------")
    doubleLinkedList.remove_first()
    doubleLinkedList.remove_first()
    doubleLinkedList.add_first(555)
    doubleLinkedList.remove_first()
    doubleLinkedList.add_first(666)
    for value in doubleLinkedList:
        print(value)
    print("---------------------")
    doubleLinkedList.remove_first()
    doubleLinkedList.remove_first()
    doubleLinkedList.remove_first()
    doubleLinkedList.remove_first()
    doubleLinkedList.remove_first()
    doubleLinkedList.remove_first()
    doubleLinkedList.add_first(1111)
    doubleLinkedList.add_first(2222)
    doubleLinkedList.add(3333)
    doubleLinkedList.add(4444)
    for value in doubleLinkedList:
        print(value)
    print("---------------------")
    doubleLinkedList.remove_value(1111)
    doubleLinkedList.remove_value(4444)
    doubleLinkedList.add(5555)
    doubleLinkedList.add(6666)
    doubleLinkedList.remove_value(2222)
    doubleLinkedList.remove_value(3333)
    doubleLinkedList.add_first(1)
    doubleLinkedList.add(2)
    doubleLinkedList.add(3)
    for value in doubleLinkedList:
        print(value)